package net.projecteuler.prob;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import net.projecteuler.util.FactorUtil;

public class Problem29 implements Runnable {

	private boolean[][] distinctTable = null;
	private boolean[] powerTable = null;
	
	private int[][] divisorTable = null;
	
	public Problem29(){
		distinctTable = new boolean[101][101];
		for(int i = 0; i < 101; i++)
			for(int j = 0; j < 101; j++)
				distinctTable[i][j] = true;
		
		powerTable = new boolean[101];
		for(int i = 2; i <= 10; i++){
			int power = i;
			for(int j = 0; j < 6; j++){
				power *= i;
				if(power > 100)
					break;
				
				powerTable[power] = true;
			}
		}
		
		divisorTable = new int[101][];
		for(int i = 2; i < 101; i++){
			divisorTable[i] = FactorUtil.divisors(i);
		}
	}
	
	@Override
	public void run() {
		List<PowerInfo> powerList = new ArrayList<PowerInfo>(99 * 99);
		
		for(int a = 2; a <= 100; a++){
			double aLog = Math.log(a);
			int[][] factors = FactorUtil.primeFactorization(a); 
			
			for(int b = 2; b <= 100; b++){
				PowerInfo powerInfo = new PowerInfo();
				powerInfo.a = a;
				powerInfo.b = b;
				powerInfo.logValue = aLog * b;
				powerInfo.factors = new int[factors.length][2];
				for(int i = 0; i < factors.length; i++){
					powerInfo.factors[i][0] = factors[i][0];
					powerInfo.factors[i][1] = factors[i][1] * b;
				}
				
				powerList.add(powerInfo);
			}
		}
		
		Comparator<PowerInfo> comparator = new Comparator<Problem29.PowerInfo>() {
			@Override
			public int compare(PowerInfo o1, PowerInfo o2) {
				if(o1.logValue > o2.logValue) return 1;
				else if(o1.logValue < o2.logValue) return -1;
				return 0;
			}
		};
		
		Collections.sort(powerList, comparator);
		
		int duplicateCnt = 0;
		for(int i = 1; i < powerList.size(); i++){
			if(powerList.get(i).equals(powerList.get(i-1)))
				duplicateCnt++;
		}
		
		System.out.println(duplicateCnt + " duplicate entrys");
		System.out.println((99 * 99 - duplicateCnt) + " distinct entrys");
	}
	
	private class PowerInfo{
		int a;
		int b;
		int[][] factors;
		double logValue;
		
		public boolean equals(PowerInfo other){
			if(this.factors.length != other.factors.length)
				return false;
			
			for(int i = 0; i < this.factors.length; i++){
				if(this.factors[i][0] != other.factors[i][0])
					return false;
				if(this.factors[i][1] != other.factors[i][1])
					return false;
			}
			
			return true;
		}
	}
}
